#include <bits/stdc++.h>
using namespace std;

struct TreeNode
{
    TreeNode *left;
    TreeNode *right;
    int val;
};

class Solution
{
public:
    vector<vector<int>> ret;
    vector<int> tmp;
    vector<vector<int>> pathSum(TreeNode *root, int targetSum)
    {
        int sum = 0;
        dfs(root, sum, targetSum);
        return ret;
    }

    void dfs(TreeNode *root, int sum, int targetSum)
    {
        if (root == nullptr)
        {
            return;
        }
        tmp.push_back(root->val);
        sum += root->val;

        if (root->left == nullptr && root->right == nullptr)
        {
            if (targetSum == sum)
            {
                ret.push_back(tmp);
                tmp.pop_back();
                return;
            }
        }
        dfs(root->left, sum, targetSum);
        dfs(root->right, sum, targetSum);

        tmp.pop_back();
    }
};
